package com.ljy.kotlindemo.leetcode

import java.util.*
import kotlin.collections.ArrayList
import kotlin.collections.HashMap
import kotlin.collections.HashSet
import kotlin.math.min

/**
 * @Author:         LiuJinYang
 * @CreateDate:     2021/7/13
 * @Description: 覃超-算法面试40讲
 */
fun main() {
    Solution().init()
}

class Solution {
    fun init() {
        //链表相关：
        n206_ReverseLinkedList()
        n24_swapPairs()
        n141_hasCycle()
        n142_detectCycle()
        n25_reverseKGroup()
        //堆栈&队列
        n20_isValid()
        n225_MyStack()
        n232_MyQueue()
        n703_KthLargest()
        n239_maxSlidingWindow()
        //哈希表
        n242_isAnagram()
        n01_twoSum()
        _0015_threeSum()
        _0018_fourSum()
        //二叉树
        n98_isValidBST()
        n236_lowestCommonAncestor()
        n235_lowestCommonAncestorBinarySearch()
        _0050_myPow()
        n169_majorityElement()
        //深度优先搜索，广度优先搜索
        n102_levelOrder()
        n104_maxDepth()
        n111_minDepth()
        _0022_generateParenthesis()
        //剪枝
        n51_solveNQueens()
        _0036_isValidSudoku()
        _0037_solveSudoku()
        //二分查找
        n69_mySqrt()
        //字典树
        n208_Trie()
        n212_findWords()
        //位运算
        n191_hammingWeight()
        n231_isPowerOfTwo()
        n338_countBits()
        n52_totalNQueens()
        //动态规划
        n70_climbStairs()
        n120_minimumTotal()
        n152_maxProduct()
        _0121_maxProfit()
        _0122_maxProfit2()
        _0123_maxProfit3()
        _0188_maxProfit4()
        _0309_maxProfit5()
        _0714_maxProfit6()
        n300_lengthOfLIS()
        n322_coinChange()
        n72_minDistance()
        //并查集
        n200_numIslands()
        //LRUCache
        n146_LRUCache()
    }

    /**
     * 146. LRU 缓存机制
    运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
    实现 LRUCache 类：
    LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
    int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
    void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
    进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
    示例：
    输入
    ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
    [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
    输出
    [null, null, null, 1, null, -1, null, -1, 3, 4]
    解释
    LRUCache lRUCache = new LRUCache(2);
    lRUCache.put(1, 1); // 缓存是 {1=1}
    lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
    lRUCache.get(1);    // 返回 1
    lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
    lRUCache.get(2);    // 返回 -1 (未找到)
    lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
    lRUCache.get(1);    // 返回 -1 (未找到)
    lRUCache.get(3);    // 返回 3
    lRUCache.get(4);    // 返回 4
    提示：
    1 <= capacity <= 3000
    0 <= key <= 10000
    0 <= value <= 105
    最多调用 2 * 105 次 get 和 put
     */
    private fun n146_LRUCache() {
        val lRUCache = LRUCache(2);
        lRUCache.put(1, 1)
        println(lRUCache.toString()) // 缓存是 {1=1}
        lRUCache.put(2, 2)// 缓存是 {1=1, 2=2}
        println(lRUCache.toString())
        println(lRUCache[1])    // 返回 1
        lRUCache.put(3, 3)// 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        println(lRUCache.toString())
        println(lRUCache[2])   // 返回 -1 (未找到)
        lRUCache.put(4, 4) // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        println(lRUCache.toString())
        println(lRUCache[1])    // 返回 -1 (未找到)
        println(lRUCache[3])    // 返回 3
        println(lRUCache[4])   // 返回 4
    }

    private class LRUCache(private val capacity: Int) {

        inner class DLinkedNode {
            var key = 0
            var value = 0
            var prev: DLinkedNode? = null
            var next: DLinkedNode? = null

            constructor() {}
            constructor(_key: Int, _value: Int) {
                key = _key
                value = _value
            }

            override fun toString(): String {
                return "{key=${key},value=${value}}"
            }
        }

        private val cache: MutableMap<Int, DLinkedNode> = java.util.HashMap()
        private var size = 0
        private val head: DLinkedNode = DLinkedNode()
        private val tail: DLinkedNode = DLinkedNode()
        operator fun get(key: Int): Int {
            val node = cache[key] ?: return -1
            // 如果 key 存在，先通过哈希表定位，再移到头部
            moveToHead(node)
            return node.value
        }

        fun put(key: Int, value: Int) {
            val node = cache[key]
            if (node == null) {
                // 如果 key 不存在，创建一个新的节点
                val newNode: DLinkedNode = DLinkedNode(key, value)
                // 添加进哈希表
                cache[key] = newNode
                // 添加至双向链表的头部
                addToHead(newNode)
                ++size
                if (size > capacity) {
                    // 如果超出容量，删除双向链表的尾部节点
                    val tail = removeTail()
                    // 删除哈希表中对应的项
                    cache.remove(tail!!.key)
                    --size
                }
            } else {
                // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
                node.value = value
                moveToHead(node)
            }
        }

        private fun addToHead(node: DLinkedNode) {
            node.prev = head
            node.next = head.next
            head.next!!.prev = node
            head.next = node
        }

        private fun removeNode(node: DLinkedNode?) {
            node!!.prev!!.next = node.next
            node.next!!.prev = node.prev
        }

        private fun moveToHead(node: DLinkedNode) {
            removeNode(node)
            addToHead(node)
        }

        private fun removeTail(): DLinkedNode? {
            val res = tail.prev
            removeNode(res)
            return res
        }

        init {
            // 使用伪头部和伪尾部节点
            head.next = tail
            tail.prev = head
        }

        override fun toString(): String {
            return cache.toString()
        }

    }

    /**
     * 200. 岛屿数量
    给你一个由'1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
    岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
    此外，你可以假设该网格的四条边均被水包围。
    示例 1：
    输入：grid = [
    ["1","1","1","1","0"],
    ["1","1","0","1","0"],
    ["1","1","0","0","0"],
    ["0","0","0","0","0"]
    ]
    输出：1
    示例 2：
    输入：grid = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
    ]
    输出：3
    提示：
    m == grid.length
    n == grid[i].length
    1 <= m, n <= 300
    grid[i][j] 的值为 '0' 或 '1'
    通过次数278,522提交次数511,042
     */
    private fun n200_numIslands() {
        println(
            numIslands(
                arrayOf(
                    charArrayOf('1', '1', '1', '1', '0'),
                    charArrayOf('1', '1', '0', '1', '0'),
                    charArrayOf('1', '1', '0', '0', '0'),
                    charArrayOf('0', '0', '0', '0', '0'),
                )
            )
        )
        println(
            numIslands(
                arrayOf(
                    charArrayOf('1', '1', '0', '0', '0'),
                    charArrayOf('1', '1', '0', '0', '0'),
                    charArrayOf('0', '0', '1', '0', '0'),
                    charArrayOf('0', '0', '0', '1', '1'),
                )
            )
        )
    }

    private class UnionFind(grid: Array<CharArray>) {
        var count = 0
        var parent: IntArray
        var rank: IntArray
        fun find(i: Int): Int {
            if (parent[i] != i) parent[i] = find(parent[i])
            return parent[i]
        }

        fun union(x: Int, y: Int) {
            val rootx = find(x)
            val rooty = find(y)
            if (rootx != rooty) {
                if (rank[rootx] > rank[rooty]) {
                    parent[rooty] = rootx
                } else if (rank[rootx] < rank[rooty]) {
                    parent[rootx] = rooty
                } else {
                    parent[rooty] = rootx
                    rank[rootx] += 1
                }
                --count
            }
        }

        init {
            val m = grid.size
            val n: Int = grid[0].size
            parent = IntArray(m * n)
            rank = IntArray(m * n)
            for (i in 0 until m) {
                for (j in 0 until n) {
                    if (grid[i][j] == '1') {
                        parent[i * n + j] = i * n + j
                        ++count
                    }
                    rank[i * n + j] = 0
                }
            }
        }
    }

    private fun numIslands(grid: Array<CharArray>): Int {
        if (grid.isEmpty() || grid[0].isEmpty()) return 0
        val uf = UnionFind(grid)
        val directions =
            arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(-1, 0), intArrayOf(1, 0))
        val m = grid.size
        val n = grid[0].size
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (grid[i][j] == '0')
                    continue
                for (d in directions) {
                    val nr = i + d[0]
                    val nc = j + d[1]
                    if (nr >= 0 && nc >= 0 && nr < m && nc < n && grid[nr][nc] == '1')
                        uf.union(i * n + j, nr * n + nc)
                }
            }
        }
        return uf.count
    }

    /**
     * 72. 编辑距离
    给你两个单词word1 和word2，请你计算出将word1转换成word2 所使用的最少操作数。
    你可以对一个单词进行如下三种操作：
    插入一个字符
    删除一个字符
    替换一个字符
    示例1：
    输入：word1 = "horse", word2 = "ros"
    输出：3
    解释：
    horse -> rorse (将 'h' 替换为 'r')
    rorse -> rose (删除 'r')
    rose -> ros (删除 'e')
    示例2：
    输入：word1 = "intention", word2 = "execution"
    输出：5
    解释：
    intention -> inention (删除 't')
    inention -> enention (将 'i' 替换为 'e')
    enention -> exention (将 'n' 替换为 'x')
    exention -> exection (将 'n' 替换为 'c')
    exection -> execution (插入 'u')
    提示：
    0 <= word1.length, word2.length <= 500
    word1 和 word2 由小写英文字母组成
     */
    private fun n72_minDistance() {
        println(
            "编辑距离: 输入：word1 = \"horse\", word2 = \"ros\", " +
                    "输出：${minDistance("horse", "ros")}"
        )
        println(
            "编辑距离: 输入：word1 = \"intention\", word2 = \"execution\", " +
                    "输出：${minDistance("intention", "execution")}"
        )
    }

    private fun minDistance(word1: String, word2: String): Int {
        val m = word1.length
        val n = word2.length
        if (m * n == 0) return m + n
        val dp = Array(m + 1) { IntArray(n + 1) }
        for (i in 0..m)
            dp[i][0] = i

        for (j in 0..n)
            dp[0][j] = j

        for (i in 1..m)
            for (j in 1..n)
                dp[i][j] = Math.min(
                    dp[i - 1][j - 1] + if (word1[i - 1] == word2[j - 1]) 0 else 1,
                    Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
                )
        return dp[m][n]
    }

    /**
     * 322. 零钱兑换
    给定不同面额的硬币 coins 和一个总金额 amount。
    编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
    如果没有任何一种硬币组合能组成总金额，返回-1。
    你可以认为每种硬币的数量是无限的。
    示例1：
    输入：coins = [1, 2, 5], amount = 11
    输出：3
    解释：11 = 5 + 5 + 1
    示例 2：
    输入：coins = [2], amount = 3
    输出：-1
    示例 3：
    输入：coins = [1], amount = 0
    输出：0
    示例 4：
    输入：coins = [1], amount = 1
    输出：1
    示例 5：
    输入：coins = [1], amount = 2
    输出：2
    提示：
    1 <= coins.length <= 12
    1 <= coins[i] <= 231 - 1
    0 <= amount <= 104
     */
    private fun n322_coinChange() {
        println(
            "零钱兑换: 输入：coins = [1, 2, 5], amount = 11," +
                    "输出：${coinChange(intArrayOf(1, 2, 5), 11)}"
        )
    }

    private fun coinChange(coins: IntArray, amount: Int): Int {
        val max = amount + 1
        val dp = IntArray(amount + 1)
        Arrays.fill(dp, max)
        dp[0] = 0
        for (i in 1..amount) {
            for (j in coins.indices) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)
                    print("coins[${j}]=${coins[j]}, ")
                    println("dp[${i}]=${dp[i]}")
                }
            }
        }
        return if (dp[amount] > amount) -1 else dp[amount]
    }

    /**
     * 300. 最长 递增(上升) 子序列
    给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
    子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
    例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
    示例 1：
    输入：nums = [10,9,2,5,3,7,101,18]
    输出：4
    解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
    示例 2：
    输入：nums = [0,1,0,3,2,3]
    输出：4
    示例 3：
    输入：nums = [7,7,7,7,7,7,7]
    输出：1
    提示：
    1 <= nums.length <= 2500
    -104 <= nums[i] <= 104
    进阶：
    你可以设计时间复杂度为 O(n2) 的解决方案吗？
    你能将算法的时间复杂度降低到 O(n log(n)) 吗?
     */
    private fun n300_lengthOfLIS() {
        println(
            "[10,9,2,5,3,7,101,18]最长递增子序列:${
                lengthOfLIS(
                    intArrayOf(
                        10,
                        9,
                        2,
                        5,
                        3,
                        7,
                        101,
                        18
                    )
                )
            }"
        )
        println("[0,1,0,3,2,3]最长递增子序列:${lengthOfLIS(intArrayOf(0, 1, 0, 3, 2, 3))}")
        println("[7,7,7,7,7,7,7]最长递增子序列:${lengthOfLIS(intArrayOf(7, 7, 7, 7, 7, 7, 7))}")
    }

    /**
     * 动态规划法
     */
    private fun lengthOfLIS(nums: IntArray): Int {
        if (nums.isEmpty()) return 0
        var result = 1
        val dp = IntArray(nums.size + 1)
        Arrays.fill(dp, 1)
//        for (i in nums.indices)
//            dp[i] = 1
        for (i in 1 until nums.size) {
            for (j in 0 until i) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1)
                }
            }
            result = Math.max(result, dp[i])
        }
        println("dp=" + dp.asList())
        return result
    }

    /**
     * 152. 乘积最大子数组
    给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
    示例 1:
    输入: [2,3,-2,4]
    输出: 6
    解释: 子数组 [2,3] 有最大乘积 6。
    示例 2:
    输入: [-2,0,-1]
    输出: 0
    解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
     */
    private fun n152_maxProduct() {
        println("乘积最大子数组:输入: [2,3,-2,4],输出:${maxProduct(intArrayOf(2, 3, -2, 4))}")
        println("乘积最大子数组:输入: [-2,0,-1],输出:${maxProduct(intArrayOf(-2, 0, -1))}")
        println("乘积最大子数组:输入: [-2,-1,0],输出:${maxProduct(intArrayOf(-2, -1, 0))}")
        println("乘积最大子数组:输入: [-4,-3,-2],输出:${maxProduct(intArrayOf(-4, -3, -2))}")
    }

    private fun maxProduct(nums: IntArray): Int {
        if (nums.isEmpty()) return 0
        var result = nums[0]
        var curMax = nums[0]
        var curMin = nums[0]
        for (i in 1 until nums.size) {
            val num = nums[i]
            val tempMax = Math.max(Math.max(curMax * num, curMin * num), num)
            curMin = Math.min(Math.min(curMax * num, curMin * num), num)
            curMax = tempMax
            result = Math.max(curMax, result)
        }
        return result
    }

    /**
     * 120. 三角形最小路径和
    给定一个三角形 triangle ，找出自顶向下的最小路径和。
    每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
    也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
    示例 1：
    输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
    输出：11
    解释：如下面简图所示：
    2
    3 4
    6 5 7
    4 1 8 3
    自顶向下的最小路径和为  11（即，2 + 3 + 5 + 1 = 11）。
    示例 2：
    输入：triangle = [[-10]]
    输出：-10
    提示：
    1 <= triangle.length <= 200
    triangle[0].length == 1
    triangle[i].length == triangle[i - 1].length + 1
    -104 <= triangle[i][j] <= 104
    进阶：
    你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？
     */
    private fun n120_minimumTotal() {
        println(
            "输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]], " +
                    "输出：${
                        minimumTotal(
                            listOf(
                                listOf(2), listOf(3, 4),
                                listOf(6, 5, 7), listOf(4, 1, 8, 3)
                            )
                        )
                    }"
        )
    }

    private fun minimumTotal(triangle: List<List<Int>>): Int {
        val mini = triangle[triangle.size - 1].toMutableList()
        for (i in triangle.size - 2 downTo 0)
            for (j in triangle[i].indices)
                mini[j] = triangle[i][j] + min(mini[j], mini[j + 1])
        return mini[0]
    }

    /**
     * 70. 爬楼梯
    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
    注意：给定 n 是一个正整数。
    示例 1：
    输入： 2
    输出： 2
    解释： 有两种方法可以爬到楼顶。
    1.  1 阶 + 1 阶
    2.  2 阶
    示例 2：
    输入： 3
    输出： 3
    解释： 有三种方法可以爬到楼顶。
    1.  1 阶 + 1 阶 + 1 阶
    2.  1 阶 + 2 阶
    3.  2 阶 + 1 阶
     */
    private fun n70_climbStairs() {
        println("n=1,爬楼梯:${climbStairs(1)}")
        println("n=2,爬楼梯:${climbStairs(2)}")
        println("n=3,爬楼梯:${climbStairs(3)}")
        println("n=4,爬楼梯:${climbStairs(4)}")
    }

    private fun climbStairs(n: Int): Int {
        if (n <= 2) return n
        val mem = IntArray(n)
        mem[0] = 1
        mem[1] = 2
        for (i in 2 until n) {
            mem[i] = mem[i - 1] + mem[i - 2]
        }
        return mem[n - 1]
    }

    /**
     * 52. N皇后 II
    n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
    给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
    示例 1：
    输入：n = 4
    输出：2
    解释：如上图所示，4 皇后问题存在两个不同的解法。
    示例 2：
    输入：n = 1
    输出：1
    提示：
    1 <= n <= 9
    皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
     */
    private fun n52_totalNQueens() {
        println("n=4,N皇后 II: ${totalNQueens(4)}")
        println("n=1,N皇后 II: ${totalNQueens(1)}")
    }

    /**
     * 位运算
     */
    private fun totalNQueens(n: Int): Int {
        var count = 0
        fun dfs(n: Int, row: Int, columns: Int, pie: Int, na: Int) {
            if (row >= n) {
                count += 1
                return
            }
            //得到当前所有的空位
            var bits = (1 shl n) - 1 and (columns or pie or na).inv()
            while (bits != 0) {
                //取到最低位的1
                val position = bits and -bits
                dfs(
                    n, row + 1, columns or position,
                    pie or position shl 1, na or position shr 1
                )
                //去掉最低位的1
                bits = bits and bits - 1
            }
        }
        dfs(n, 0, 0, 0, 0)
        return count
    }

    /**
     * 338. 比特位计数
    给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
    示例 1:
    输入: 2
    输出: [0,1,1]
    示例 2:
    输入: 5
    输出: [0,1,1,2,1,2]
    进阶:
    给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
    要求算法的空间复杂度为O(n)。
    你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。
     */
    private fun n338_countBits() {
        println("n=2,比特位计数:" + countBits(2).asList())
        println("n=5,比特位计数:" + countBits(5).asList())
    }

    private fun countBits(n: Int): IntArray {
        val bits = IntArray(n + 1)
        var highBit = 0
        for (i in 1..n) {
            if (i and i - 1 == 0) {
                highBit = i
            }
            bits[i] = bits[i - highBit] + 1
        }
        return bits
    }

    /**
     * 231. 2 的幂
    给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
    如果存在一个整数 x 使得n == 2x ，则认为 n 是 2 的幂次方。
    示例 1：
    输入：n = 1
    输出：true
    解释：20 = 1
    示例 2：
    输入：n = 16
    输出：true
    解释：24 = 16
    示例 3：
    输入：n = 3
    输出：false
    示例 4：
    输入：n = 4
    输出：true
    示例 5：
    输入：n = 5
    输出：false
    提示：
    -231 <= n <= 231 - 1
    进阶：你能够不使用循环/递归解决此问题吗？
     */
    private fun n231_isPowerOfTwo() {
        println("n=1,2的n次幂：${isPowerOfTwo(1)}")
        println("n=3,2的n次幂：${isPowerOfTwo(3)}")
        println("n=4,2的n次幂：${isPowerOfTwo(4)}")
    }

    private fun isPowerOfTwo(n: Int): Boolean {
        return n > 0 && (n and n - 1) == 0
    }

    /**
     * 191. 位1的个数
    编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
    提示：
    请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
    在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的示例 3中，输入表示有符号整数 -3。
    示例 1：
    输入：00000000000000000000000000001011
    输出：3
    解释：输入的二进制串 00000000000000000000000000001011中，共有三位为 '1'。
    示例 2：
    输入：00000000000000000000000010000000
    输出：1
    解释：输入的二进制串 00000000000000000000000010000000中，共有一位为 '1'。
    示例 3：
    输入：11111111111111111111111111111101
    输出：31
    解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
    提示：
    输入必须是长度为 32 的 二进制串 。
    进阶：
    如果多次调用这个函数，你将如何优化你的算法？
     */
    private fun n191_hammingWeight() {
        println("n=11,位1的个数:${hammingWeight(11)}")
    }

    /**
     * 位运算
     */
    private fun hammingWeight(n: Int): Int {
        var n = n
        var ret = 0
        while (n != 0) {
            n = n and n - 1
            ret++
        }
        return ret
    }

    /**
     * 212. 单词搜索 II
     * 给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。
    单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
    示例 1：
    输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
    输出：["eat","oath"]
    示例 2：
    输入：board = [["a","b"],["c","d"]], words = ["abcb"]
    输出：[]
    提示：
    m == board.length
    n == board[i].length
    1 <= m, n <= 12
    board[i][j] 是一个小写英文字母
    1 <= words.length <= 3 * 104
    1 <= words[i].length <= 10
    words[i] 由小写英文字母组成
    words 中的所有字符串互不相同
     */
    private fun n212_findWords() {
        val board = arrayOf(
            charArrayOf('o', 'a', 'a', 'n'),
            charArrayOf('e', 't', 'a', 'e'),
            charArrayOf('i', 'h', 'k', 'r'),
            charArrayOf('i', 'f', 'l', 'v')
        )
        val words = arrayOf("oath", "pea", "eat", "rain")
        println("单词搜索 II：${findWords(board, words)}")
    }

    /**
     * 1. DFS深度优先搜索
     * 2. 字典树
     */
    private fun findWords(board: Array<CharArray>, words: Array<String>): List<String> {
        val res = HashSet<String>()
        val trie = Trie()
        for (word in words) {
            trie.insert(word)
        }
        val m = board.size
        val n = board[0].size
        val visited = Array(m) { BooleanArray(n) }
        fun dfs(x: Int, y: Int, str: String) {
            var str = str
            if (x < 0 || x >= board.size || y < 0 || y >= board[0].size) {
                return
            }
            if (visited[x][y]) {
                return
            }
            str += board[x][y]
            if (!trie.startsWith(str)) {
                return
            }
            if (trie.search(str)) {
                res.add(str)
            }
            visited[x][y] = true
            dfs(x - 1, y, str)
            dfs(x + 1, y, str)
            dfs(x, y - 1, str)
            dfs(x, y + 1, str)
            visited[x][y] = false
        }
        for (i in 0 until m)
            for (j in 0 until n)
                dfs(i, j, "")
        return ArrayList(res)
    }

    /**
     * 208. 实现 Trie (前缀树)
    Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

    请你实现 Trie 类：

    Trie() 初始化前缀树对象。
    void insert(String word) 向前缀树中插入字符串 word 。
    boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
    boolean startsWith(String prefix) 如果之前已经插入的字符串word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
    示例：
    输入
    ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
    [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
    输出
    [null, null, true, false, true, null, true]
    解释
    Trie trie = new Trie();
    trie.insert("apple");
    trie.search("apple");   // 返回 True
    trie.search("app");     // 返回 False
    trie.startsWith("app"); // 返回 True
    trie.insert("app");
    trie.search("app");     // 返回 True
    提示：
    1 <= word.length, prefix.length <= 2000
    word 和 prefix 仅由小写英文字母组成
    insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次
     */
    private fun n208_Trie() {
        val trie = Trie();
        trie.insert("apple");
        trie.search("apple");   // 返回 True
        trie.search("app");     // 返回 False
        trie.startsWith("app"); // 返回 True
        trie.insert("app");
        trie.search("app");     // 返回 True
    }

    private class Trie {
        /** Inserts a word into the trie. */
        private val children: Array<Trie?> = arrayOfNulls(26)
        private var isEnd = false

        fun insert(word: String) {
            var node: Trie? = this
            for (element in word) {
                val index = element - 'a'
                if (node!!.children[index] == null) {
                    node.children[index] = Trie()
                }
                node = node.children[index]
            }
            node!!.isEnd = true
        }

        /** Returns if the word is in the trie. */
        fun search(word: String): Boolean {
            val node = searchPrefix(word)
            return node != null && node.isEnd
        }

        /** Returns if there is any word in the trie that starts with the given prefix. */
        fun startsWith(prefix: String): Boolean {
            return searchPrefix(prefix) != null
        }

        private fun searchPrefix(prefix: String): Trie? {
            var node: Trie? = this
            prefix.forEach { element ->
                val index = element - 'a'
                if (node!!.children[index] == null) {
                    return null
                }
                node = node!!.children[index]
            }
            return node
        }
    }

    /**
     * 69. x 的平方根
    实现 int sqrt(int x) 函数。
    计算并返回 x 的平方根，其中 x 是非负整数。
    由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
    示例 1:
    输入: 4
    输出: 2
    示例 2:
    输入: 8
    输出: 2
    说明: 8 的平方根是 2.82842...,
    由于返回类型是整数，小数部分将被舍去。
     */
    private fun n69_mySqrt() {
        println("4的平方根：${mySqrt(4)}")
        println("8的平方根：${mySqrt(8)}")
        println("9的平方根：${mySqrt(9)}")
        println("4的平方根：${mySqrt2(4)}")
        println("8的平方根：${mySqrt2(8)}")
        println("9的平方根：${mySqrt2(9)}")
    }

    /**
     * 牛顿迭代法
     */
    private fun mySqrt2(x: Int): Int {
        var r = x
        while (r * r > x)
            r = (r + x / r) / 2
        return r
    }

    /**
     * 二分查找法
     */
    private fun mySqrt(x: Int): Int {
        if (x == 0 || x == 1) return x
        var l = 1
        var r = x
        var result = -1
        while (l <= r) {
            val mid = (l + r) / 2
            if (mid == x / mid)
                return mid
            else if (mid > x / mid)
                r = mid - 1
            else {
                l = mid + 1
                result = mid
            }
        }
        return result
    }

    /**
     * 37. 解数独
    编写一个程序，通过填充空格来解决数独问题。
    一个数独的解法需遵循如下规则：
    数字 1-9 在每一行只能出现一次。
    数字 1-9 在每一列只能出现一次。
    数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
    空白格用 '.' 表示。
    提示：
    给定的数独序列只包含数字 1-9 和字符 '.' 。
    你可以假设给定的数独只有唯一解。
    给定数独永远是 9x9 形式的。
     */
    private fun _0037_solveSudoku() {
        println("--------_0037_solveSudoku-------")
        solveSudoku(
            arrayOf(
                charArrayOf('5', '3', '.', '.', '7', '.', '.', '.', '.'),
                charArrayOf('6', '.', '.', '1', '9', '5', '.', '.', '.'),
                charArrayOf('.', '9', '8', '.', '.', '.', '.', '6', '.'),
                charArrayOf('8', '.', '.', '.', '6', '.', '.', '.', '3'),
                charArrayOf('4', '.', '.', '8', '.', '3', '.', '.', '1'),
                charArrayOf('7', '.', '.', '.', '2', '.', '.', '.', '6'),
                charArrayOf('.', '6', '.', '.', '.', '.', '2', '8', '.'),
                charArrayOf('.', '.', '.', '4', '1', '9', '.', '.', '5'),
                charArrayOf('.', '.', '.', '.', '8', '.', '.', '7', '9'),
            )
        )
    }


    private fun solveSudoku(board: Array<CharArray>) {
        helper(board)
        for (cs in board) {
            println(cs.contentToString())
        }
    }

    private fun helper(board: Array<CharArray>): Boolean {
        for (i in board.indices) {
            for (j in board[i].indices) {
                if (board[i][j] != '.')
                    continue
                for (c in '1'..'9') {
                    if (!isValidSK(board, i, j, c))
                        continue
                    board[i][j] = c
                    if (helper(board))
                        return true
                    board[i][j] = '.'
                }
                return false
            }
        }
        return true
    }

    private fun isValidSK(board: Array<CharArray>, i: Int, j: Int, c: Char): Boolean {
        for (k in 0..8) {
            if (board[k][j] != '.' && board[k][j] == c) return false
            if (board[i][k] != '.' && board[i][k] == c) return false
            val row = i / 3 * 3 + k / 3
            val col = j / 3 * 3 + k % 3
            if (board[row][col] != '.' && board[row][col] == c) return false
        }
        return true
    }

    /**
     * 36. 有效的数独
    判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
    数字 1-9 在每一行只能出现一次。
    数字 1-9 在每一列只能出现一次。
    数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
    上图是一个部分填充的有效的数独。
    数独部分空格内已填入了数字，空白格用 '.' 表示。
    示例 1:
    输入:
    [
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
    ]
    输出: true
    示例 2:
    输入:
    [
    ["8","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
    ]
    输出: false
    解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
    但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
    说明:
    一个有效的数独（部分已被填充）不一定是可解的。
    只需要根据以上规则，验证已经填入的数字是否有效即可。
    给定数独序列只包含数字 1-9 和字符 '.' 。
    给定数独永远是 9x9 形式的。
     */
    private fun _0036_isValidSudoku() {
        println("--------_0036_isValidSudoku-------")
        println(
            isValidSudoku(
                arrayOf(
                    charArrayOf('8', '3', '.', '.', '7', '.', '.', '.', '.'),
                    charArrayOf('6', '.', '.', '1', '9', '5', '.', '.', '.'),
                    charArrayOf('.', '9', '5', '.', '.', '.', '.', '6', '.'),
                    charArrayOf('8', '.', '.', '.', '6', '.', '.', '.', '3'),
                    charArrayOf('4', '.', '.', '8', '.', '3', '.', '.', '1'),
                    charArrayOf('7', '.', '.', '.', '2', '.', '.', '.', '6'),
                    charArrayOf('.', '6', '.', '.', '.', '.', '2', '8', '.'),
                    charArrayOf('.', '.', '.', '4', '1', '9', '.', '.', '5'),
                    charArrayOf('.', '.', '.', '.', '8', '.', '.', '7', '9'),
                )
            )
        )
        println(
            isValidSudoku(
                arrayOf(
                    charArrayOf('8', '3', '.', '.', '7', '.', '.', '.', '.'),
                    charArrayOf('6', '.', '.', '1', '9', '5', '.', '.', '.'),
                    charArrayOf('.', '9', '8', '.', '.', '.', '.', '6', '.'),
                    charArrayOf('8', '.', '.', '.', '6', '.', '.', '.', '3'),
                    charArrayOf('4', '.', '.', '8', '.', '3', '.', '.', '1'),
                    charArrayOf('7', '.', '.', '.', '2', '.', '.', '.', '6'),
                    charArrayOf('.', '6', '.', '.', '.', '.', '2', '8', '.'),
                    charArrayOf('.', '.', '.', '4', '1', '9', '.', '.', '5'),
                    charArrayOf('.', '.', '.', '.', '8', '.', '.', '7', '9'),
                )
            )
        )
    }

    /**
    想必数独游戏我们都玩过，就是给一个 9x9 大小的矩阵，可以分为9个 3x3 大小的矩阵，
    要求是每个小矩阵内必须都是1到9的数字不能有重复，同时大矩阵的横纵列也不能有重复数字
    在遍历每个数字的时候，就看看包含当前位置的行和列以及 3x3 小方阵中是否已经出现该数字，
    这里需要三个 boolean 型矩阵，大小跟原数组相同，分别记录各行，各列，各小方阵是否出现某个数字，
    其中行和列标志下标很好对应，就是小方阵的下标需要稍稍转换一下
    其中一维下标 n 对于3个二维数组分别表示：第 n 行，第 n 列，第 n 个子九宫格
    其中二维下标 m 对于3个二维数组分别表示：在当前行、列、子九宫格的数字m
    二维数组中的值则表示：该数字是否出现过
     */
    private fun isValidSudoku(board: Array<CharArray>): Boolean {
        val rows = Array(9) { BooleanArray(9) }
        val cols = Array(9) { BooleanArray(9) }
        val boxs = Array(9) { BooleanArray(9) }
        for (i in board.indices) {
            for (j in board[i].indices) {
                if (board[i][j] != '.') {
                    val num = board[i][j] - '0' - 1
                    val k = i / 3 * 3 + j / 3
                    if (rows[i][num] || cols[j][num] || boxs[k][num]) return false
                    rows[i][num] = cols[j][num]
                    cols[j][num] = boxs[k][num]
                    boxs[k][num] = true
                }
            }
        }
        return true
    }

    /**
     * 51. N 皇后
    n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
    给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
    每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
    示例 1：
    输入：n = 4
    输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
    解释：如上图所示，4 皇后问题存在两个不同的解法。
    示例 2：
    输入：n = 1
    输出：[["Q"]]
    提示：
    1 <= n <= 9
    皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
     */
    private fun n51_solveNQueens() {
        println("N 皇后,n=4:${solveNQueens(4)}")
        println("N 皇后,n=1:${solveNQueens(1)}")
    }

    private fun solveNQueens(n: Int): List<List<String>> {
        val solutions: MutableList<List<String>> = java.util.ArrayList()
        val queens = IntArray(n)
        Arrays.fill(queens, -1)
        val columns: MutableSet<Int> = java.util.HashSet()
        val diagonals1: MutableSet<Int> = java.util.HashSet()
        val diagonals2: MutableSet<Int> = java.util.HashSet()
        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2)
        return solutions
    }

    private fun backtrack(
        solutions: MutableList<List<String>>,
        queens: IntArray,
        n: Int,
        row: Int,
        columns: MutableSet<Int>,
        diagonals1: MutableSet<Int>,
        diagonals2: MutableSet<Int>
    ) {
        if (row == n) {
            val board = generateBoard(queens, n)
            solutions.add(board)
        } else {
            for (i in 0 until n) {
                if (columns.contains(i)) {
                    continue
                }
                val diagonal1 = row - i
                if (diagonals1.contains(diagonal1)) {
                    continue
                }
                val diagonal2 = row + i
                if (diagonals2.contains(diagonal2)) {
                    continue
                }
                queens[row] = i
                columns.add(i)
                diagonals1.add(diagonal1)
                diagonals2.add(diagonal2)
                backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2)
                queens[row] = -1
                columns.remove(i)
                diagonals1.remove(diagonal1)
                diagonals2.remove(diagonal2)
            }
        }
    }

    private fun generateBoard(queens: IntArray, n: Int): List<String> {
        val board: MutableList<String> = java.util.ArrayList()
        for (i in 0 until n) {
            val row = CharArray(n)
            Arrays.fill(row, '.')
            row[queens[i]] = 'Q'
            board.add(String(row))
        }
        return board
    }
//    fun solveNQueens(n: Int): List<List<String>> {
//        if (n < 1) return emptyList()
//        val result = ArrayList<ArrayList<String>>()
//        val cols = HashSet<Int>()
//        val pie = HashSet<Int>()
//        val na = HashSet<Int>()
//        fun _dfs(n: Int, row: Int, curState: ArrayList<String>) {
//            if (row >= n) {
//                result.add(curState)
//                return
//            }
//            for (col in 0..n) {
//                if (cols.contains(col) || pie.contains(row + col) || na.contains(row - col))
//                    continue
//                cols.add(col)
//                pie.add(row + col)
//                na.add(row - col)
//                curState.add(col.toString())
//                _dfs(n, row + 1, curState)
//                cols.remove(col)
//                pie.remove(row + col)
//                na.remove(row - col)
//            }
//
//        }
//        _dfs(n, 0, ArrayList())
//        fun _generateResult(n:Int):List<List<String>>{
//
//        }
//        return _generateResult(n)
//    }

    /**
     * 22. 括号生成
    数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
    示例：
    输入：n = 3
    输出：[
    "((()))",
    "(()())",
    "(())()",
    "()(())",
    "()()()"
    ]
     */
    private fun _0022_generateParenthesis() {
        println("--------_0022_generateParenthesis-------")
        println(generateParenthesis(1))
        println(generateParenthesis(2))
        println(generateParenthesis(3))
        println(generateParenthesis(4))
    }

    private fun generateParenthesis(n: Int): List<String> {
        val list = ArrayList<String>()
        fun _gen(left: Int, right: Int, n: Int, result: String) {
            if (left == n && right == n)
                list.add(result)
            if (left < n)
                _gen(left + 1, right, n, "$result(")
            if (left > right && right < n)
                _gen(left, right + 1, n, "$result)")
        }
        _gen(0, 0, n, "")
        return list
    }

    /**
     * 思想是找左括号，每找到一个左括号，就在其后面加一个完整的括号，最后再在开头加一个 ()，就形成了所有的情况，
     * 需要注意的是，有时候会出现重复的情况，所以用set数据结构，好处是如果遇到重复项，不会加入到结果中，
     * 最后我们再把set转为vector即可
     */
    private fun generateParenthesis2(n: Int): List<String> {
        val res = HashSet<String>()
        if (n == 0) {
            res.add("")
        } else {
            val pre = generateParenthesis(n - 1)
            for (str in pre) {
                var str = str
                for (i in str.indices) {
                    if (str[i] == '(') {
                        str = str.substring(0, i + 1) + "()" + str.substring(i + 1, str.length)
                        res.add(str)
                        str = str.substring(0, i + 1) + str.substring(i + 3, str.length)
                    }
                }
                res.add("()$str")
            }
        }
        return res.toList()
    }


    /**
     * 111. 二叉树的最小深度
    给定一个二叉树，找出其最小深度。
    最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
    说明：叶子节点是指没有子节点的节点。
    示例 1：
    输入：root = [3,9,20,null,null,15,7]
    3
    / \
    9  20
    /  \
    15   7
    输出：2
    示例 2：
    输入：root = [2,null,3,null,4,null,5,null,6]
    输出：5
    提示：
    树中节点数的范围在 [0, 105] 内
    -1000 <= Node.val <= 1000
     */
    private fun n111_minDepth() {
        val node3 = TreeNode(3)
        val node9 = TreeNode(9)
        val node20 = TreeNode(20)
        val node15 = TreeNode(15)
        val node7 = TreeNode(7)
        val node11 = TreeNode(11)
        node3.left = node9
        node3.right = node20
        node20.left = node15
        node20.right = node7
        node15.right = node11
        println("node3二叉树的最小深度:${minDepth(node3)}")
        println("node9二叉树的最小深度:${minDepth(node9)}")
        println("node15二叉树的最小深度:${minDepth(node15)}")
    }

    private fun minDepth(root: TreeNode?): Int {
        if (root == null) return 0
//        if (root.left==null) return minDepth(root.right)+1
//        if (root.right==null) return minDepth(root.left)+1
//        return 1+Math.min(minDepth(root.left),minDepth(root.right))
        val left = minDepth(root.left)
        val right = minDepth(root.right)
        return if (left == 0 || right == 0) left + right + 1 else Math.min(left, right) + 1
    }

    /**
     * 104. 二叉树的最大深度
    给定一个二叉树，找出其最大深度。
    二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
    说明:叶子节点是指没有子节点的节点。
    示例：
    给定二叉树 [3,9,20,null,null,15,7]，
    3
    / \
    9  20
    /  \
    15   7
    返回它的最大深度3 。
     */
    private fun n104_maxDepth() {
        val node3 = TreeNode(3)
        val node9 = TreeNode(9)
        val node20 = TreeNode(20)
        val node15 = TreeNode(15)
        val node7 = TreeNode(7)
        node3.left = node9
        node3.right = node20
        node20.left = node15
        node20.right = node7
        println("二叉树的最大深度:${maxDepth(node3)}")
    }

    private fun maxDepth(root: TreeNode?): Int {
        return if (root == null) 0 else 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
    }

    /**
     * 102. 二叉树的层序遍历
    给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
    示例：
    二叉树：[3,9,20,null,null,15,7],
    3
    / \
    9  20
    /  \
    15   7
    返回其层序遍历结果：
    [
    [3],
    [9,20],
    [15,7]
    ]
     */
    private fun n102_levelOrder() {
        val node3 = TreeNode(3)
        val node9 = TreeNode(9)
        val node20 = TreeNode(20)
        val node15 = TreeNode(15)
        val node7 = TreeNode(7)
        node3.left = node9
        node3.right = node20
        node20.left = node15
        node20.right = node7
        val result = levelOrder(node3)
        println("广度优先搜索:$result")
        val result2 = levelOrder2(node3)
        println("深度优先搜索+递归:$result2")
    }

    /**
     * 深度优先搜索+递归
     */
    private fun levelOrder2(root: TreeNode?): List<List<Int>> {
        if (root == null) return emptyList()
        val result = ArrayList<ArrayList<Int>>()
        fun dfs(node: TreeNode?, level: Int) {
            if (node == null) return
            if (result.size < level + 1)
                result.add(ArrayList())
            result[level].add(node.`val`.toInt())
            dfs(node.left, level + 1)
            dfs(node.right, level + 1)
        }
        dfs(root, 0)
        return result
    }


    /**
     * 广度优先搜索
     */
    private fun levelOrder(root: TreeNode?): List<List<Int>> {
        if (root == null) return emptyList()
        val result = ArrayList<ArrayList<Int>>()
        val queue = LinkedList<TreeNode>()
//        val visited=HashSet<Int>()
        queue.offer(root)
        while (!queue.isEmpty()) {
            val levelSize = queue.size
            val level = ArrayList<Int>()
            for (it in 1..levelSize) {
                val node = queue.poll()
                level.add(node.`val`.toInt())
                if (node.left != null) queue.offer(node.left)
                if (node.right != null) queue.offer(node.right)
            }
            result.add(level)
        }
        return result
    }

    /**
     * 121. 买卖股票的最佳时机
    给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
    如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
    注意：你不能在买入股票前卖出股票。
    示例 1:
    输入: [7,1,5,3,6,4]
    输出: 5
    解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
    注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
    示例 2:
    输入: [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
     */
    private fun _0121_maxProfit() {
        println("--------_0121_maxProfit-------")
        println(maxProfit(intArrayOf(7, 1, 5, 3, 6, 4)))
        println(maxProfit(intArrayOf(7, 6, 4, 3, 1)))
    }

    private fun maxProfit(prices: IntArray): Int {
        var res = 0
        var buy = Int.MAX_VALUE
        for (price in prices) {
            buy = Math.min(buy, price)
            res = Math.max(res, price - buy)
        }
        return res
    }

    /**
     * 122. 买卖股票的最佳时机 II
    给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
    设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
    注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
    示例 1:
    输入: [7,1,5,3,6,4]
    输出: 7
    解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
    随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
    示例 2:
    输入: [1,2,3,4,5]
    输出: 4
    解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
    注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
    因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
    示例 3:
    输入: [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
    提示：
    1 <= prices.length <= 3 * 10 ^ 4
    0 <= prices[i] <= 10 ^ 4
     */
    private fun _0122_maxProfit2() {
        println("--------_122_maxProfit2-------")
        println(maxProfit2(intArrayOf(7, 1, 5, 3, 6, 4)))
        println(maxProfit2(intArrayOf(1, 2, 3, 4, 5)))
        println(maxProfit2(intArrayOf(7, 6, 4, 3, 1)))
    }

    private fun maxProfit2(prices: IntArray): Int {
        var res = 0
        for (i in 0 until prices.size - 1) {
            if (prices[i] < prices[i + 1]) {
                res += prices[i + 1] - prices[i]
            }
        }
        return res
    }

    /**
    123. 买卖股票的最佳时机 III
    给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
    设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
    注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
    示例 1:
    输入: [3,3,5,0,0,3,1,4]
    输出: 6
    解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
    随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
    示例 2:
    输入: [1,2,3,4,5]
    输出: 4
    解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
    注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
    因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
    示例 3:
    输入: [7,6,4,3,1]
    输出: 0
    解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。
     */
    private fun _0123_maxProfit3() {
        println("--------_123_maxProfit3-------")
        println(maxProfit3(intArrayOf(3, 3, 5, 0, 0, 3, 1, 4)))
        println(maxProfit3(intArrayOf(1, 2, 3, 4, 5)))
        println(maxProfit3(intArrayOf(7, 6, 4, 3, 1)))
    }

    private fun maxProfit3(prices: IntArray): Int {
        val len = prices.size
        if (len < 2)
            return 0
        // 第 1 维的 0 没有意义，1 表示交易进行第一笔，2 表示交易进行第二笔
        // 为了使得第 1 维的数值 1 和 2 有意义，这里将第 1 维的长度设置为 3
        //第2维，1表示买入，0表示卖出
        val dp = Array(3) { IntArray(2) }
        //规定了必须持股，因此是 -prices[0]
        dp[1][1] = -prices[0]
        //还没发生的交易，持股的时候应该初始化为负无穷
        dp[2][1] = Int.MIN_VALUE
        for (i in 1 until len) {
            dp[1][1] = Math.max(dp[1][1], -prices[i])
            dp[1][0] = Math.max(dp[1][0], dp[1][1] + prices[i])
            dp[2][1] = Math.max(dp[2][1], dp[1][0] - prices[i])
            dp[2][0] = Math.max(dp[2][0], dp[2][1] + prices[i])
        }
        return Math.max(dp[1][0], dp[2][0])
    }

    /**
    188. 买卖股票的最佳时机 IV
    给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
    设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
    注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
    示例 1：
    输入：k = 2, prices = [2,4,1]
    输出：2
    解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
    示例 2：
    输入：k = 2, prices = [3,2,6,5,0,3]
    输出：7
    解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
    随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
    提示：
    0 <= k <= 109
    0 <= prices.length <= 1000
    0 <= prices[i] <= 1000
     */
    private fun _0188_maxProfit4() {
        println("--------_0188_maxProfit4-------")
        println(maxProfit4(2, intArrayOf(3, 3, 5, 0, 0, 3, 1, 4)))
        println(maxProfit4(2, intArrayOf(1, 2, 3, 4, 5)))
        println(maxProfit4(2, intArrayOf(7, 6, 4, 3, 1)))
    }

    private fun maxProfit4(k: Int, prices: IntArray): Int {
        val len = prices.size
        if (k == 0 || len < 2)
            return 0
        if (k > len / 2)
            return greedy(prices)
        val dp = Array(k + 1) { IntArray(2) }
        for (i in 0..k)
            dp[i][1] = Int.MIN_VALUE

        for (p in prices)
            for (j in 1..k) {
                dp[j][1] = Math.max(dp[j][1], dp[j - 1][0] - p)
                dp[j][0] = Math.max(dp[j][0], dp[j][1] + p)
            }
        return dp[k][0]
    }

    private fun greedy(prices: IntArray): Int {
        var res = 0
        for (i in 1 until prices.size) {
            if (prices[i] > prices[i - 1]) {
                res += prices[i] - prices[i - 1]
            }
        }
        return res
    }

    /**
    309. 最佳买卖股票时机含冷冻期
    给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
    设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
    你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
    卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
    示例:
    输入: [1,2,3,0,2]
    输出: 3
    解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
     */
    private fun _0309_maxProfit5() {
        println("--------_0309_maxProfit5-------")
        println(maxProfit5(intArrayOf(1, 2, 3, 0, 2)))
    }

    private fun maxProfit5(prices: IntArray): Int {
        val len = prices.size
        if (len < 2) {
            return 0
        }
        val dp = IntArray(3)
        dp[0] = 0
        dp[1] = -prices[0]
        dp[2] = 0
        var pre0 = dp[0]
        var pre2 = dp[2]
        for (i in 1 until len) {
            dp[0] = Math.max(dp[0], pre2)
            dp[1] = Math.max(dp[1], pre0 - prices[i])
            dp[2] = dp[1] + prices[i]
            pre0 = dp[0]
            pre2 = dp[2]
        }
        return Math.max(dp[0], dp[2])
    }

    /**
    714. 买卖股票的最佳时机含手续费
    给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
    你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
    返回获得利润的最大值。
    注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
    示例 1:
    输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
    输出: 8
    解释: 能够达到的最大利润:
    在此处买入 prices[0] = 1
    在此处卖出 prices[3] = 8
    在此处买入 prices[4] = 4
    在此处卖出 prices[5] = 9
    总利润:  ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
    注意:
    0 < prices.length <= 50000.
    0 < prices[i] < 50000.
    0 <= fee < 50000.
     */
    private fun _0714_maxProfit6() {
        println("--------_0714_maxProfit6-------")
        println(maxProfit6(intArrayOf(1, 3, 2, 8, 4, 9), 2))
    }

    private fun maxProfit6(prices: IntArray, fee: Int): Int {
        val len = prices.size
        if (len < 2) {
            return 0
        }
        // j = 0 表示不持股，j = 1 表示持股
        // 并且规定在买入股票的时候，扣除手续费
        val dp = IntArray(2)
        dp[0] = 0
        dp[1] = -prices[0] - fee
        for (i in 1 until len) {
            dp[0] = Math.max(dp[0], dp[1] + prices[i])
            dp[1] = Math.max(dp[1], dp[0] - prices[i] - fee)
        }
        return dp[0]
    }

    /**
     * 169. 多数元素/求众数
    给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 n/2 的元素。
    你可以假设数组是非空的，并且给定的数组总是存在多数元素。
    示例1：
    输入：[3,2,3]
    输出：3
    示例2：
    输入：[2,2,1,1,1,2,2]
    输出：2
    进阶：
    尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
     */
    private fun n169_majorityElement() {
        println("n169_majorityElement-排序法：" + majorityElement(intArrayOf(2, 2, 1, 1, 1, 2, 2)))
        println("n169_majorityElement-哈希表-map：" + majorityElement2(intArrayOf(2, 2, 1, 1, 1, 2, 2)))
    }

    /**
     * 哈希表-map
     */
    private fun majorityElement2(nums: IntArray): Int {
        val counts = HashMap<Int, Int>()
        for (it in nums) {
            counts[it] = (counts[it] ?: 0) + 1
        }
        var max = 0
        var maxKey: Int = Int.MIN_VALUE
        counts.forEach {
            if (it.value > max) {
                max = it.value
                maxKey = it.key
            }
        }
        return maxKey
    }

    /**
     * 排序法
     */
    private fun majorityElement(nums: IntArray): Int {
        Arrays.sort(nums)
        return nums[nums.size / 2]
    }

    /**
     * 50. Pow(x, n)
    实现 pow(x, n) ，即计算 x 的 n 次幂函数。
    示例 1:
    输入: 2.00000, 10
    输出: 1024.00000
    示例 2:
    输入: 2.10000, 3
    输出: 9.26100
    示例 3:
    输入: 2.00000, -2
    输出: 0.25000
    解释: 2-2 = 1/22 = 1/4 = 0.25
    说明:
    -100.0 < x < 100.0
    n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

     */
    private fun _0050_myPow() {
        println("--------_0050_myPow-------")
        println(myPow(2.0, 10))
        println(myPow(2.1, 3))
        println(myPow(2.0, -2))
        println(myPow2(2.0, 10))
        println(myPow2(2.1, 3))
        println(myPow2(2.0, -2))
    }

    private fun myPow2(x: Double, n: Int): Double {
        var x = x
        var n = n
        if (n < 0) {
            x = 1 / x
            n = -n
        }
        var pow = 1.0
        while (n > 0) {
            if (n % 2 == 1)
                pow *= x
            x *= x
            n /= 2
        }
        return pow
    }

    private fun myPow(x: Double, n: Int): Double {
        if (n == 0) return 1.0
        if (n == Int.MIN_VALUE) return 1 / x * myPow(x, n + 1)
        if (n < 0) return 1 / myPow(x, -n)
        if (n % 2 == 1) return x * myPow(x, n - 1)
        return myPow(x * x, n / 2)
    }


    /**
     * 236. 二叉树的最近公共祖先
    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
    百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，
    满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
    示例 1：
    输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
    输出：3
    解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
    示例 2：
    输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
    输出：5
    解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
    示例 3：
    输入：root = [1,2], p = 1, q = 2
    输出：1
    提示：
    树中节点数目在范围 [2, 105] 内。
    -109 <= Node.val <= 109
    所有 Node.val 互不相同 。
    p != q
    p 和 q 均存在于给定的二叉树中。
     */
    private fun n236_lowestCommonAncestor() {
        val node0 = TreeNode(0)
        val node1 = TreeNode(1)
        val node2 = TreeNode(2)
        val node3 = TreeNode(3)
        val node4 = TreeNode(4)
        val node5 = TreeNode(5)
        val node6 = TreeNode(6)
        val node7 = TreeNode(7)
        val node8 = TreeNode(8)
        node3.left = node5
        node3.right = node1
        node5.left = node6
        node5.right = node2
        node2.left = node7
        node2.right = node4
        node1.left = node0
        node1.right = node8
        println("node5,node1:" + lowestCommonAncestor(node3, node5, node1)?.`val`)
        println("node6,node4:" + lowestCommonAncestor(node3, node6, node4)?.`val`)
        println("node7,node5:" + lowestCommonAncestor(node3, node7, node5)?.`val`)

    }

    private fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
        if (root == null || root == p || root == q) return root
        val left = lowestCommonAncestor(root.left, p, q)
        val right = lowestCommonAncestor(root.right, p, q)
        return if (left == null) right else if (right == null) left else root
    }

    /**
     * 235. 二叉搜索树的最近公共祖先
    给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
    百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
    满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
    例如，给定如下二叉搜索树:  root = [ 6,2,8,0,4,7,9,null,null,3,5]
    示例 1:
    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
    输出: 6
    解释: 节点 2 和节点 8 的最近公共祖先是 6。
    示例 2:
    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
    输出: 2
    解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
    说明:
    所有节点的值都是唯一的。
    p、q 为不同节点且均存在于给定的二叉搜索树中。
     */
    private fun n235_lowestCommonAncestorBinarySearch() {
        val node1 = TreeNode(1)
        val node2 = TreeNode(2)
        val node3 = TreeNode(3)
        val node4 = TreeNode(4)
        val node5 = TreeNode(5)
        val node6 = TreeNode(6)
        val node7 = TreeNode(7)
        val node8 = TreeNode(8)
        val node9 = TreeNode(9)
        node6.left = node2
        node6.right = node8
        node2.left = node1
        node2.right = node4
        node4.left = node3
        node4.right = node5
        node8.left = node7
        node8.right = node9
        println("node2,node8:" + lowestCommonAncestorBinarySearch(node6, node2, node8)?.`val`)
        println("node2,node5:" + lowestCommonAncestorBinarySearch(node6, node2, node5)?.`val`)
        println("node1,node3:" + lowestCommonAncestorBinarySearch(node6, node1, node3)?.`val`)
        println("node1,node3:" + lowestCommonAncestorBinarySearch(node6, node1, node3)?.`val`)
    }

    private fun lowestCommonAncestorBinarySearch(
        root: TreeNode?,
        p: TreeNode?,
        q: TreeNode?
    ): TreeNode? {
        if (p?.`val` ?: 0 < root?.`val` ?: 0 && q?.`val` ?: 0 < root?.`val` ?: 0)
            return lowestCommonAncestorBinarySearch(root?.left, p, q)
        if (p?.`val` ?: 0 > root?.`val` ?: 0 && q?.`val` ?: 0 > root?.`val` ?: 0)
            return lowestCommonAncestorBinarySearch(root?.right, p, q)
        return root
    }

    /**
     * 98. 验证二叉搜索树
    给定一个二叉树，判断其是否是一个有效的二叉搜索树。
    假设一个二叉搜索树具有如下特征：
    节点的左子树只包含小于当前节点的数。
    节点的右子树只包含大于当前节点的数。
    所有左子树和右子树自身必须也是二叉搜索树。
    示例 1:
    输入:
    2
    / \
    1   3
    输出: true
    示例 2:
    输入:
    5
    / \
    1   4
    / \
    3   6
    输出: false
    解释: 输入为: [5,1,4,null,null,3,6]。
    根节点的值为 5 ，但是其右子节点值为 4 。

     */
    private fun n98_isValidBST() {
        val node1 = TreeNode(1)
        val node2 = TreeNode(2)
        val node3 = TreeNode(3)
        node2.left = node1
        node2.right = node3
        println("isValidBST(node2):" + isValidBST(node2))
        val node4 = TreeNode(4)
        val node5 = TreeNode(5)
        node4.right = node5
        println("isValidBST(node4):" + isValidBST(node4))
        val node6 = TreeNode(6)
        val node7 = TreeNode(7)
        node6.left = node7
        println("isValidBST(node6):" + isValidBST(node6))
    }

    private fun isValidBST(root: TreeNode?): Boolean {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE)
    }

    private fun isValidBST(node: TreeNode?, min: Long?, max: Long?): Boolean {
        if (node == null) return true
        if (min == null || node.`val` <= min) return false
        if (max == null || node.`val` >= max) return false
        return isValidBST(node.left, min, node.`val`) && isValidBST(node.right, node.`val`, max)
    }

    class TreeNode(var `val`: Long) {
        var left: TreeNode? = null
        var right: TreeNode? = null
    }

    /**
     * 18. 四数之和
    给定一个包含n 个整数的数组nums和一个目标值target，判断nums中是否存在四个元素 a，b，c和 d,
    使得a + b + c + d的值与target相等？找出所有满足条件且不重复的四元组。
    注意：
    答案中不可以包含重复的四元组。
    示例：
    给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
    满足要求的四元组集合为：
    [
    [-1,  0, 0, 1],
    [-2, -1, 1, 2],
    [-2,  0, 0, 2]
    ]
     */
    private fun _0018_fourSum() {
        println("--------_0018_fourSum-------")
        println(fourSum(intArrayOf(1, 0, -1, 0, -2, 2), 0))
    }

    private fun fourSum(nums: IntArray?, target: Int): List<List<Int>> {
        if (nums == null || nums.size < 4) return ArrayList()
        val res = ArrayList<List<Int>>()
        val n = nums.size
        Arrays.sort(nums)
        for (i in 0..n - 3) {
            if (i > 0 && nums[i] == nums[i - 1]) continue
            for (j in i + 1..n - 2) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue
                var left = j + 1
                var right = n - 1
                while (left < right) {
                    val sum = nums[i] + nums[j] + nums[left] + nums[right]
                    if (sum == target) {
                        val oneResult = arrayListOf(nums[i], nums[j], nums[left], nums[right])
                        res.add(oneResult)
                        while (left < right && nums[left] == nums[left + 1]) left++
                        while (left < right && nums[right] == nums[right - 1]) right--
                        left++
                        right--
                    } else if (sum < target) {
                        left++
                    } else right--
                }
            }
        }
        return res
    }

    /**
     * 15. 三数之和
    给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
    请你找出所有满足条件且不重复的三元组。
    注意：答案中不可以包含重复的三元组。
    示例：
    给定数组 nums = [-1, 0, 1, 2, -1, -1,1,-4]，
    满足要求的三元组集合为：
    [
    [-1, 0, 1],
    [-1, -1, 2]
    ]

     */
    private fun _0015_threeSum() {
        println("--------_015_threeSum-------")
        println(threeSum(intArrayOf(-1, 0, 1, -2, 2, 2, -1, -1, 1, -4)).toString())
    }

    private fun threeSum(nums: IntArray?): List<List<Int>> {
        if (nums == null || nums.size < 3) return ArrayList()
        Arrays.sort(nums)
        val ret = LinkedList<List<Int>>()
        val set = HashSet<List<Int>>()
        for (i in 0..nums.size - 2) {
            if (i > 0 && nums[i] == nums[i - 1]) continue//对i去重
            var start = i + 1
            var end = nums.size - 1
            while (start < end) {
                if (nums[i] + nums[start] + nums[end] == 0) {
                    val oneResult = LinkedList<Int>()
                    oneResult.add(nums[i])
                    oneResult.add(nums[start])
                    oneResult.add(nums[end])
                    set.add(oneResult)
                    start++
                    end--
                } else {
                    if (nums[i] + nums[start] + nums[end] < 0) {
                        start++
                    } else {
                        end--
                    }
                }
            }
        }
        ret.addAll(set)
        return ret
    }

    /**
     * 1. 两数之和
    给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，
    并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
    示例:
    给定 nums = [2, 7, 11, 15], target = 9
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]
     */
    private fun n01_twoSum() {
        val nums = intArrayOf(1, 2, 11, 7, 15)
        for (i in twoSum(nums, 9)!!) {
            println(i)
        }
    }

    private fun twoSum(nums: IntArray, target: Int): IntArray? {
        val map = HashMap<Int, Int>()
        for (i in nums.indices) {
            if (map.containsKey(target - nums[i])) {
                return intArrayOf(map[target - nums[i]]!!, i)
            }
            map[nums[i]] = i
        }
        return null
    }

    /**
     * 242. 有效的字母异位词
    给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
    示例1:
    输入: s = "anagram", t = "nagaram"
    输出: true
    示例 2:
    输入: s = "rat", t = "car"
    输出: false
    提示:
    1 <= s.length, t.length <= 5 * 104
    s 和 t 仅包含小写字母
    进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
     */
    private fun n242_isAnagram() {
        val s = "aacc"
        val t = "ccac"
        println("s=${s},t=${t}, 哈希表-isAnagram(s,t):${isAnagram(s, t)}")
        println("s=${s},t=${t}, 数组排序-isAnagram2(s,t):${isAnagram2(s, t)}")
        val s2 = "aabcd"
        val t2 = "adcba"
        println("s=${s2},t=${t2}, 哈希表-isAnagram(s,t):${isAnagram(s2, t2)}")
        println("s=${s2},t=${t2}, 数组排序-isAnagram(s,t):${isAnagram2(s2, t2)}")
    }

    /**
     * 哈希表
     */
    private fun isAnagram(s: String, t: String): Boolean {
        if (s.length != t.length)
            return false
        val dic1 = emptyMap<Char, Int>().toMutableMap()
        val dic2 = emptyMap<Char, Int>().toMutableMap()
        for (it in s) {
            dic1[it] = (dic1[it] ?: 0) + 1
        }
        for (it in t) {
            dic2[it] = (dic2[it] ?: 0) + 1
        }
        println(dic1.toString())
        println(dic2.toString())
        return dic1 == dic2
    }

    /**
     * 数组排序-偷懒
     */
    private fun isAnagram2(s: String, t: String): Boolean {
        if (s.length != t.length)
            return false
        val arr1 = s.toCharArray()
        val arr2 = t.toCharArray()
        Arrays.sort(arr1)
        Arrays.sort(arr2)
        println(arr1.asList().toString())
        println(arr2.asList().toString())
        return Arrays.equals(arr1, arr2)
    }

    /**
     * 239. 滑动窗口最大值
     * 给你一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。
     * 你只可以看到在滑动窗口内的 k个数字。滑动窗口每次只向右移动一位。
    返回滑动窗口中的最大值。
    示例 1：
    输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
    输出：[3,3,5,5,6,7]
    解释：
    滑动窗口的位置                最大值
    ---------------               -----
    [1  3  -1] -3  5  3  6  7       3
    1 [3  -1  -3] 5  3  6  7       3
    1  3 [-1  -3  5] 3  6  7       5
    1  3  -1 [-3  5  3] 6  7       5
    1  3  -1  -3 [5  3  6] 7       6
    1  3  -1  -3  5 [3  6  7]      7
    示例 2：
    输入：nums = [1], k = 1
    输出：[1]
    示例 3：
    输入：nums = [1,-1], k = 1
    输出：[1,-1]
    示例 4：
    输入：nums = [9,11], k = 2
    输出：[11]
    示例 5：
    输入：nums = [4,-2], k = 2
    输出：[4]
     */
    private fun n239_maxSlidingWindow() {
        val arr = intArrayOf(1, 3, -1, -3, 5, 3, 6, 7)
        val k = 3
        print("arr=${arr.asList()},k=${k}时：")
        println(maxSlidingWindow(arr, k).asList().toString())
    }


    private fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        //判空
        if (nums.isEmpty()) return nums
        val pq = PriorityQueue<IntArray> { pair1, pair2 ->
            if (pair1[0] != pair2[0]) pair2[0] - pair1[0] else pair2[1] - pair1[1]
        }
        for (i in 0 until k) {
            pq.offer(intArrayOf(nums[i], i))
        }
        val result = IntArray(nums.size - k + 1)
        result[0] = pq.peek()[0]
        for (i in k until nums.size) {
            pq.offer(intArrayOf(nums[i], i))
            while (pq.peek()[1] <= i - k) {
                pq.poll()
            }
            result[i - k + 1] = pq.peek()[0]
        }
        return result
    }

    /**
     * 703 数据流中的第 K 大元素
     * 设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
    请实现 KthLargest 类：
    KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
    int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

    示例：
    输入：
    ["KthLargest", "add", "add", "add", "add", "add"]
    [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
    输出：
    [null, 4, 5, 5, 8, 8]
    解释：
    KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
    kthLargest.add(3);   // return 4
    kthLargest.add(5);   // return 5
    kthLargest.add(10);  // return 5
    kthLargest.add(9);   // return 8
    kthLargest.add(4);   // return 8
     */
    private fun n703_KthLargest() {
        val obj = KthLargest(3, intArrayOf(1, 2, 3))
        obj.print()
        println("obj.add(4):" + obj.add(4))
        obj.print()
        println("obj.add(8):" + obj.add(8))
        obj.print()
        println("obj.add(6):" + obj.add(6))
        obj.print()
    }

    /**
     * 优先队列
     */
    private class KthLargest(k: Int, nums: IntArray) {
        private val k: Int = k
        private val pq: PriorityQueue<Int> = PriorityQueue()

        init {
            for (x in nums) {
                add(x)
            }
        }

        fun add(n: Int): Int {
            if (pq.size < k)
                pq.offer(n)
            else if (pq.peek() < n) {
                pq.poll()
                pq.offer(n)
            }
            return pq.peek()
        }

        fun print() {
            println(pq.toString())
        }

    }

    /**
     * 232. 用栈实现队列
     * 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
    实现 MyQueue 类：
    void push(int x) 将元素 x 推到队列的末尾
    int pop() 从队列的开头移除并返回元素
    int peek() 返回队列开头的元素
    boolean empty() 如果队列为空，返回 true ；否则，返回 false

    说明：
    你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
    你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

    进阶：
    你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

    示例：
    输入：
    ["MyQueue", "push", "push", "peek", "pop", "empty"]
    [[], [1], [2], [], [], []]
    输出：
    [null, null, null, 1, 1, false]
    解释：
    MyQueue myQueue = new MyQueue();
    myQueue.push(1); // queue is: [1]
    myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
    myQueue.peek(); // return 1
    myQueue.pop(); // return 1, queue is [2]
    myQueue.empty(); // return false
     */
    private fun n232_MyQueue() {
        val obj = MyQueue()
        println("用栈实现队列:")
        println("obj.push(1):" + obj.push(1))
        println("obj.push(2):" + obj.push(2))
        println("obj.pop():" + obj.pop())
        println("obj.pop():" + obj.pop())
        println("obj.empty():" + obj.empty())
    }

    private class MyQueue() {
        private val stack1: Stack<Int>
        private val stack2: Stack<Int>

        /** Initialize your data structure here. */
        init {
            stack1 = Stack<Int>()
            stack2 = Stack<Int>()
        }

        /** Push element x to the back of queue. */
        fun push(x: Int) {
            stack1.push(x)
        }

        /** Removes the element from in front of queue and returns that element. */
        fun pop(): Int {
            if (stack2.isEmpty()) {
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop())
                }
            }
            return stack2.pop()
        }

        /** Get the front element. */
        fun peek(): Int {
            if (stack2.isEmpty()) {
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop())
                }
            }
            return stack2.peek()
        }

        /** Returns whether the queue is empty. */
        fun empty(): Boolean {
            return stack1.isEmpty() && stack2.isEmpty()
        }

    }

    /**
     * 225. 用队列实现栈
     * 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
    实现 MyStack 类：
    void push(int x) 将元素 x 压入栈顶。
    int pop() 移除并返回栈顶元素。
    int top() 返回栈顶元素。
    boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

    注意：
    你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
    你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。


    示例：
    输入：
    ["MyStack", "push", "push", "top", "pop", "empty"]
    [[], [1], [2], [], [], []]
    输出：
    [null, null, null, 2, 2, false]
    解释：
    MyStack myStack = new MyStack();
    myStack.push(1);
    myStack.push(2);
    myStack.top(); // 返回 2
    myStack.pop(); // 返回 2
    myStack.empty(); // 返回 False
     */
    private fun n225_MyStack() {
        println("用队列实现栈:")
        val obj = MyStack()
        println("obj.push(1):" + obj.push(1))
        println("obj.push(2):" + obj.push(2))
        println("obj.pop():" + obj.pop())
        println("obj.pop():" + obj.pop())
        println("obj.empty():" + obj.empty())
    }

    class MyStack() {
        private var queue1: Queue<Int>
        private var queue2: Queue<Int>

        /** Initialize your data structure here. */
        init {
            queue1 = LinkedList()
            queue2 = LinkedList()
        }


        /** Push element x onto stack. */
        fun push(x: Int) {
            queue2.offer(x)
            //Queue 中 add() 和 offer()都是用来向队列添加一个元素。
            //在容量已满的情况下，add() 方法会抛出IllegalStateException异常，offer() 方法只会返回 false 。
            while (!queue1.isEmpty()) {
                queue2.offer(queue1.poll())
            }
            val temp = queue1
            queue1 = queue2
            queue2 = temp
        }

        /** Removes the element on top of the stack and returns that element. */
        fun pop(): Int {
            return queue1.poll()
        }

        /** Get the top element. */
        fun top(): Int {
            return queue1.peek()
        }

        /** Returns whether the stack is empty. */
        fun empty(): Boolean {
            return queue1.isEmpty()
        }

    }

    /**
     * 20. 有效的括号
    给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
    有效字符串需满足：
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
    注意空字符串可被认为是有效字符串。
    示例 1:
    输入: "()"
    输出: true
    示例 2:
    输入: "()[]{}"
    输出: true
    示例 3:
    输入: "(]"
    输出: false
    示例 4:
    输入: "([)]"
    输出: false
    示例 5:
    输入: "{[]}"
    输出: true
     */
    private fun n20_isValid() {
        println("--------_0020_isValid-------")
        println(isValid("()"))
        println(isValid("()[]{}"))
        println(isValid("(]"))
        println(isValid("{[]}"))
    }

    /**
     * 这里需要用一个栈，开始遍历输入字符串，如果当前字符为左半边括号时，则将其压入栈中，如果遇到右半边括号时，
     * 若此时栈为空，则直接返回 false，如不为空，则取出栈顶元素，若为对应的左半边括号，则继续循环，反之返回 false，代码如下：
     */
    private fun isValid(s: String): Boolean {
        val stack = Stack<Char>()
        val parenMap: HashMap<Char, Char> = hashMapOf(')' to '(', ']' to '[', '}' to '{')
        for (c in s)
            if (!parenMap.containsKey(c))
                stack.push(c)
            else if (stack.isEmpty() || parenMap[c] != stack.pop())
                return false
        return stack.isEmpty()
    }

    private fun isValid2(s: String): Boolean {
        val stack = Stack<Char>()
        for (i in s.indices) {
            val c = s[i]
            if (c == '(' || c == '{' || c == '[')
                stack.push(c)
            else {
                if (stack.isEmpty()) return false
                if (c == ')' && stack.peek() != '(') return false
                if (c == ']' && stack.peek() != '[') return false
                if (c == '}' && stack.peek() != '{') return false
                stack.pop()
            }
        }
        return stack.isEmpty()
    }

    /**
     * 25. K 个一组翻转链表 : reverse-nodes-in-k-group
     * 给你一个链表，每个节点一组进行翻转，请你返回翻转后的链表。
    k是一个正整数，它的值小于或等于链表的长度。
    如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。
     */
    private fun n25_reverseKGroup() {
        val ln1 = ListNode(1)
        val ln2 = ListNode(2)
        val ln3 = ListNode(3)
        val ln4 = ListNode(4)
        val ln5 = ListNode(5)
        ln1.next = ln2
        ln2.next = ln3
        ln3.next = ln4
        ln4.next = ln5
        println("原链表：")
        printListNode(ln1)
        println("k个一组反转后的链表：")
        val ln = reverseKGroup(ln1, 3)
        printListNode(ln)
    }

    /**
     * 首先遍历整个链表，统计出链表的长度，然后如果长度大于等于k，交换节点，当 k=2 时，每段只需要交换一次，
     * 当 k=3 时，每段需要交换2此，所以i从1开始循环，注意交换一段后更新 pre 指针，然后 num 自减k，
     * 直到 num<k 时循环结束
     */
    private fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
        val dummy = ListNode(-1)
        var pre: ListNode? = dummy
        var cur: ListNode? = pre
        dummy.next = head
        var num = 0
        while (cur?.next != null) {
            cur = cur.next
            ++num
        }
        while (num >= k) {
            cur = pre?.next
            for (i in 1 until k) {
                val temp = cur?.next
                cur?.next = temp?.next
                temp?.next = pre?.next
                pre?.next = temp
            }
            pre = cur
            num -= k
        }
        return dummy.next
    }


    /**
     * 142. 环形链表 II
     * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回  null。
    为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
    如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
    说明：不允许修改给定的链表。
     */
    private fun n142_detectCycle() {
        val ln1 = ListNode(1)
        val ln2 = ListNode(2)
        val ln3 = ListNode(3)
        val ln4 = ListNode(4)
        val ln5 = ListNode(5)
        ln1.next = ln2
        ln2.next = ln3
        ln3.next = ln4
        ln4.next = ln5
        println("原链表：")
        printListNode(ln1)
        println("哈希表 开始入环的第一个节点：")
        println(detectCycle(ln1)?.value)
        ln5.next = ln3
        println("修改 ln5.next = ln3")
        println("哈希表 开始入环的第一个节点：")
        println(detectCycle(ln1)?.value)
    }

    /**
     * 哈希表法
     */
    private fun detectCycle(head: ListNode?): ListNode? {
        var pos = head
        val visited = HashSet<ListNode>()
        while (pos != null) {
            if (!visited.add(pos))
                return pos
            pos = pos.next
        }
        return null
    }

    /**
     * 141. 环形链表
     * 给定一个链表，判断链表中是否有环。
    如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
    为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
    如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
    如果链表中存在环，则返回 true 。 否则，返回 false
     */
    private fun n141_hasCycle() {
        val ln1 = ListNode(1)
        val ln2 = ListNode(2)
        val ln3 = ListNode(3)
        val ln4 = ListNode(4)
        val ln5 = ListNode(5)
        ln1.next = ln2
        ln2.next = ln3
        ln3.next = ln4
        ln4.next = ln5
        println("原链表：")
        printListNode(ln1)
        println("哈希表-借助set 判断是否有环：")
        println(hasCycle(ln1))
        println("快慢指针法判断是否有环：")
        println(hasCycle2(ln1))
        ln5.next = ln3
        println("修改 ln5.next = ln3")
        println("哈希表-借助set 判断是否有环：")
        println(hasCycle(ln1))
        println("快慢指针法判断是否有环：")
        println(hasCycle2(ln1))
    }


    /**
     * 快慢指针法判断是否有环
     */
    private fun hasCycle2(head: ListNode?): Boolean {
        if (head == null || head.next == null)
            return false
        var slow = head
        var fast = head.next
        while (slow != fast) {
            if (fast == null || fast.next == null)
                return false
            slow = slow?.next
            fast = fast.next?.next
        }
        return true
    }

    /**
     * 哈希表-借助set 判断是否有环
     */
    private fun hasCycle(head: ListNode?): Boolean {
        var pos = head
        val visited = HashSet<ListNode>()
        while (pos != null) {
            if (!visited.add(pos))
                return true
            pos = pos.next
        }
        return false
    }

    /**
     * 24. 两两交换链表中的节点
    Given a linked list, swap every two adjacent nodes and return its head.
    You may not modify the values in the list's nodes, only nodes itself may be changed.
    Example:
    Given 1->2->3->4, you should return the list as 2->1->4->3.
     */
    private fun n24_swapPairs() {
        val ln1 = ListNode(1)
        val ln2 = ListNode(2)
        val ln3 = ListNode(3)
        val ln4 = ListNode(4)
        val ln5 = ListNode(5)
        ln1.next = ln2
        ln2.next = ln3
        ln3.next = ln4
        ln4.next = ln5
        println("原链表：")
        printListNode(ln1)
        val ln = swapPairs(ln1)
        println("递归法交换后链表：")
        printListNode(ln)
    }


    /**
     * 递归法实现链表节点交换
     */
    private fun swapPairs(head: ListNode?): ListNode? {
        if (head?.next == null) return head
        val t: ListNode? = head.next
        head.next = swapPairs(head.next?.next)
        t?.next = head
        return t
    }

    /**
     * 206. Reverse Linked List（反转链表）
    Reverse a singly linked list.
    Example:
    Input: 1->2->3->4->5->NULL
    Output: 5->4->3->2->1->NULL
    Follow up:
    A linked list can be reversed either iteratively or recursively. Could you implement both?
     */
    private fun n206_ReverseLinkedList() {
        val ln1 = ListNode(1)
        val ln2 = ListNode(2)
        val ln3 = ListNode(3)
        val ln4 = ListNode(4)
        val ln5 = ListNode(5)
        ln1.next = ln2
        ln2.next = ln3
        ln3.next = ln4
        ln4.next = ln5
        println("原链表：")
        printListNode(ln1)
        val ln = reverseList(ln1)
        println("循环法反转后链表：")
        printListNode(ln)
        val ln21 = ListNode(21)
        val ln22 = ListNode(22)
        val ln23 = ListNode(23)
        val ln24 = ListNode(24)
        val ln25 = ListNode(25)
        ln21.next = ln22
        ln22.next = ln23
        ln23.next = ln24
        ln24.next = ln25
        println("原链表：")
        printListNode(ln21)
        val ln20 = reverseList2(ln21)
        println("递归法反转后链表：")
        printListNode(ln20)

    }


    /**
     * 循环法实现反转链表
     *
     */
    private fun reverseList(head: ListNode?): ListNode? {
        var head = head
        var newHead: ListNode? = null
        while (head != null) {
            val t = head.next
            head.next = newHead
            newHead = head
            head = t
        }
        return newHead
    }

    /**
     * 递归法实现反转链表
     *
     */
    private fun reverseList2(head: ListNode?): ListNode? {
        if (head?.next == null) return head
        val newHead = reverseList(head.next)
        head.next?.next = head
        head.next = null
        return newHead
    }

    class ListNode(var value: Int) {
        var next: ListNode? = null
    }

    private fun printListNode(head: ListNode?) {
        print("-->${head?.value}")
        if (head?.next != null)
            printListNode(head.next)
        else
            println("\n>>> end <<<")
    }

}


